Graphe de Petersen généralisé

Le graphe de Dürer G (6, 2).

En théorie des graphes, les graphes de Petersen généralisés sont une famille de graphes cubiques formés en connectant les sommets d'un polygone régulier aux sommets correspondants d'un polygone régulier étoilé. Ils comprennent le graphe de Petersen et généralisent l'une des manières de construire le graphe de Petersen. La famille des graphes de Petersen généralisés a été introduite en 1950 par H. S. M. Coxeter et a reçu son nom en 1969 par Mark Watkins.

Définition et notation

Dans la notation introduite par Watkins, G(n,k) est un graphe avec un ensemble de 2n sommets

$\{u_{0},u_{1},\ldots ,u_{n-1},v_{0},v_{1},\ldots ,v_{n-1}\}$

et ensemble d'arêtes

$\{u_{i}u_{i+1},u_{i}v_{i},v_{i}v_{i+k}\mid 0\leq i\leq n-1\}$

où les indices sont modulo n et k < n /2. Certains auteurs utilisent la notation GPG(n,k). La notation de Coxeter pour le même graphe est {n} + {n/k} ; c'est une combinaison des symboles de Schläfli pour le polygone régulier et pour le polygone régulier étoilé à partir desquels le graphe est formé. Le graphe de Petersen lui-même est le graphe G(5,2), resp. {5} + {5/2}.

Tout graphe de Petersen généralisé peut également être construit à partir d'un graphe de tension (en) avec deux sommets, deux boucles et une autre arête.

Exemples

Parmi les graphes de Petersen généralisés il y a les graphes prismatiques G(n,1), le graphe de Dürer G(6,2), le graphe de Möbius-Kantor G(8, 3), le dodécaèdre G(10,2), le graphe de Desargues G(10,3) et le graphe de Nauru G(12,5).

Quatre graphes de Petersen généralisés, à savoir le 3-prisme, le 5-prisme, le graphe de Dürer et G(7,2), font partie des sept graphes cubiques, 3-sommet-connexes et « bien couverts » (ce qui signifie que tous leurs ensembles indépendants maximaux ont même taille).

Propriétés

L'un des trois cycles hamiltoniens de G(9,2). Les deux autres cycles hamiltoniens du même graphe sont symétriques dans des rotations de 40° du dessin.

La famille des graphes de Petersen généralisés possède un certain nombre de propriétés remarquables, parmi lesquelles les suivantes :

• G(n,k) est sommet-transitif (ce qui signifie qu'il a des automorphismes qui envoient tout sommet sur tout autre sommet) si et seulement si (n,k) = (10, 2) ou k² ≡ ±1 (mod n ).

• G(n,k) est arête-transitif (il existe des automorphismes de toute arête sur toute autre arête) dans les seuls sept cas suivants : (n,k) = (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), (24, 5). Ces sept graphes sont donc les seuls graphes de Petersen généralisés symétriques. Donc le graphe de Nauru est un des sept graphes de Petersen généralisés symétriques. Ces sept sont le graphe hexaédrique $G(4,1)$, le graphe de Petersen $G(5,2)$, le graphe de Möbius-Kantor $G(8,3)$, le graphe dodécaédrique $G(10,2)$, le graphe de Desargues $G(10,3)$ et le graphe de Nauru $G(24,5)$.

• G(n,k) est biparti si et seulement si n est pair et k est impair.

• G(n,k) est un graphe de Cayley si et seulement si k ² ≡ 1 (mod n ).

• G(n,k) est hypohamiltonien lorsque n est congru à 5 modulo 6 et k = 2, k =n − 2, ou k = (n ± 1)/2 (ces quatre choix de k conduisent à des graphes isomorphes). Il est également non hamiltonien lorsque n est divisible par 4, au moins égal à 8, et k = n/2. Dans tous les autres cas, il possède un cycle hamiltonien. Quand n est congru à 3 modulo 6, G(n,2) a exactement trois cycles hamiltoniens . Pour G(n,2), le nombre de cycles hamiltoniens peut être calculé par une formule qui dépend de la classe de congruence de n modulo 6 et fait intervenir les nombres de Fibonacci.

• Tout graphe de Petersen généralisé est un graphe distance-unité.

Isomorphismes

G(n,k) est isomorphe à G(n,l) si et seulement si kl ≡ ±1 (mod n ).

Mailles

La maille de G(n,k ) est égale au moins à 3 et au plus à 8, en particulier :

$g(G(n,k))\leq \min \left\{8,k+3,{\frac {n}{\gcd(n,k)}}\right\}.$

Voici un tableau avec les valeurs exactes des mailles :

Condition	Maille
$n=3k$	3
$n=4k$	4
$k=1$
$n=5k$	5
$n=5k/2$
$k=2$
$n=6k$	6
$k=3$
$n=2k+2$
$n=7k$	7
$n=7k/2$
$n=7k/3$
$k=4$
$n=2k+3$
$n=3k\pm 2$
sinon	8

Nombre chromatique et index chromatique

En tant que graphes réguliers, et selon le théorème de Brooks, le nombre chromatique d'un graphe de Petersen généralisé ne peut être supérieur à son degré . Les graphes de Petersen généralisés sont cubiques, leur nombre chromatique est donc 2 ou 3. Plus précisément, on a :

$\chi (G(n,k))={\begin{cases}2&{\text{si}}\ n\ {\text{est pair et}}\ k\ {\text{est impair}}\\3&{\text{si}}\ n\ {\text{est impair et}}\ k\ {\text{est pair}}\\\end{cases}}$

Par exemple, le nombre chromatique de $G(5,2)$ est 3.

• 
  Une 3-coloration du graphe de Petersen $G(5,2)$
• 
  Une 2-coloration du graphe de Desargues $G(10,3)$
• 
  Une 3-coloration du graphe de Dürer $G(6,2)$

Le graphe de Petersen, qui est un snark, a un indice chromatique égal à 4. Tous les autres graphes de Petersen généralisés ont l'indice chromatique égal à 3.

Le graphe de Petersen généralisé G(9, 2) est l'un des rares graphes connus pour ne posséder qu'une seule 3-coloration des arêtes.

• 
  Une 4-coloration des arêtes du graphe de Petersen $G(5,2)$
• 
  Une 3-coloration des arêtes du graphe de Dürer $G(6,2)$
• 
  Une 3-coloration des arêtes du dodécaèdre $G(10,2)$
• 
  Une 3-coloration des arêtes du graphe de Desargues $G(10,3)$
• 
  Une 3-colorationdes arêtes du graphe de Nauru $G(12,5)$

Le graphe de Petersen lui-même est le seul graphe de Petersen généralisé qui n'est pas 3-arêtes coloriable.

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Generalized Petersen graph » (voir la liste des auteurs).